package leetcode.L46;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution1 {
    //标记数组
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> list1 = new LinkedList<>();
    int[] flag;

    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0) {
            return list;
        }
        flag = new int[nums.length];
        backtrack(nums, 0, flag);
        return list;
    }

    private void backtrack(int[] nums, int start, int[] flag) {
        if (list1.size() == nums.length) {
            list.add(new ArrayList<>(list1));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (flag[i] != 1) {
                list1.add(nums[i]);
                flag[i] = 1;
                backtrack(nums, i + 1, flag);
                list1.remove(list1.size() - 1);
                flag[i] = 0;
            }
        }
    }
}